#include <bits/stdc++.h>

using namespace std;

// 最大矩形
// 给定一个仅包含 0 和 1 、大小为 rows * cols 的二维二进制矩阵
// 找出只包含 1 的最大矩形，并返回其面积
// 测试链接：https://leetcode.cn/problems/maximal-rectangle/

class Solution 
{
private:
    static const int MAXN = 201;
    int height[MAXN];
    int st[MAXN], r;

    int largestRectangleArea(int n)
    {
        r = 0; 
        int ans = 0, cur, left;
        for(int i = 0; i < n; ++i)
        {
            while(r > 0 && height[st[r - 1]] >= height[i])
            {
                cur = st[--r];
                left = r > 0 ? st[r - 1] : -1;
                ans = max(ans, (i - left - 1) * height[cur]);
            }
            st[r++] = i;
        }

        while(r > 0)
        {
            cur = st[--r];
            left = r > 0 ? st[r - 1] : -1;
            ans = max(ans, (n - left - 1) * height[cur]);
        }
        return ans;
    }

public:
    int maximalRectangle(vector<vector<char>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        fill(height, height + m, 0);
        int ans = 0;
        for(int i = 0; i < m; ++i)
        {
            // 来到i行，长方形一定要以i行做底！
			// 加工高度数组(压缩数组)
            for(int j = 0; j < n; ++j)
            {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            ans = max(ans, largestRectangleArea(n));
        }
        return ans;
    }
};